public class LeetCode912 {
    /**
     * 对给定的整数数组进行堆排序。
     *
     * @param nums 需要排序的整数数组
     * @return 排序后的整数数组
     */
    public int[] sortArray(int[] nums) {
        // 构建最大堆：将数组转换为最大堆结构
        buildMaxHeap(nums);

        // 排序过程：
        // 每次取出堆顶元素（最大值），放到数组末尾，并调整剩余部分为新的最大堆
        for (int i = nums.length - 1; i > 0; i--) {
            // 交换堆顶元素（最大值）与当前堆的最后一个元素
            swap(nums, 0, i);
            // 减少堆的大小，忽略新的最后一个元素（它已经在正确的位置）
            // 对新的堆顶元素执行下沉操作，保持最大堆性质
            maxHeapify(nums, i, 0);
        }

        return nums;
    }

    /**
     * 构建最大堆：从最后一个非叶子节点开始向上调整，确保每个子树都满足最大堆性质。
     *
     * @param nums 要构建的最大堆数组
     */
    private void buildMaxHeap(int[] nums) {
        int len = nums.length;
        // 最后一个非叶子节点的索引是 (len / 2) - 1
        // 从最后一个非叶子节点开始向上调整
        for (int i = len / 2 - 1; i >= 0; i--) {
            maxHeapify(nums, len, i);
        }
    }

    /**
     * 维持最大堆性质：通过比较和交换操作确保指定节点及其子树符合最大堆的要求。
     *
     * @param nums     数组表示的堆
     * @param heapSize 当前堆的大小
     * @param i        需要调整的节点索引
     */
    private void maxHeapify(int[] nums, int heapSize, int i) {
        int largest = i; // 初始化最大值为根节点
        int left = 2 * i + 1; // 左子节点索引
        int right = 2 * i + 2; // 右子节点索引

        // 如果左子节点存在且大于根节点，则更新最大值
        if (left < heapSize && nums[left] > nums[largest]) {
            largest = left;
        }

        // 如果右子节点存在且大于当前最大值，则更新最大值
        if (right < heapSize && nums[right] > nums[largest]) {
            largest = right;
        }

        // 如果最大值不是根节点，则交换并继续下沉
        if (largest != i) {
            swap(nums, i, largest); // 交换根节点和最大值
            // 继续对交换后的子树进行 maxHeapify，以维持最大堆性质
            maxHeapify(nums, heapSize, largest);
        }
    }

    /**
     * 交换数组中的两个元素。
     *
     * @param nums 数组
     * @param i    第一个元素的索引
     * @param j    第二个元素的索引
     */
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
